ProgrammingAlgorithm

백준 11066 파일합치기

Dynamic Programming

파일 합치기 문제는 인접한 파일을 합치고 합쳐진 파일을 다른 파일과 합쳐나가며 이 파일을 합치는데 필요한 비용을 최소화 하는 문제이다. 이 문제는 동적 계획법으로 풀 수 있다.

이 부분에 대한 개념은 구간에 대한 개념으로 나누어 보면 쉽게 풀 수 있다. 1 ~ n까지의 구간이 있다고 하면 1~n까지의 구간의 합을 최소로 만드는 것은 임의의 j에 대하여 1~j, j+1 ~ n 까지의 구간을 합쳐서 그 합을 최소로 만드는 것과 같다. 즉 구간 i~j라고 함은 i~j의 구간의 파일의 크기의 최소 합이다.

이에 대한 점화식을 세우면 for(int j=1;j<=n;j++) cost(1)(n) = min(cost(1)(n),cost(1)(j) + cost(j+1)(n))으로 부분으로 나올 수 있는 모든 구간들에 대해 확인하고 그 최소 값을 찾는다. 또한 크기가 큰 구간을 찾기 위해서는 크기가 작은 구간의 값들을 알아햐 하므로 크기가 작은 값들부터 계산해서 점차적으로 값을 계산해 나간다.

부분 구간들 또한 더 작은 부분 구간들의 최소합으로 이루어진 결과이므로 결과적으로 최소 + 최소를 만족하여 답을 구할 수 있게 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#pragma warning(disable:4996)
#include<iostream>
#include<string.h>
#include<vector>
#include<cmath>
#include<queue>
#include<algorithm>
#define INF 987654321
using namespace std;

int testCase;

int sum[502];
int cost[502][502];

int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d", &testCase);

	for (int t = 0; t < testCase; t++)
	{
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
		{
			int numb;
			scanf("%d", &numb);
			sum[i] = sum[i - 1] + numb;
		}

		for (int k = 1; k < n; k++)
		{
			for (int i = 1; i <= n - k; i++)
			{
				cost[i][i + k] = INF;
				for (int j = i; j < i + k ; j++)
				{
					cost[i][i + k] = min(cost[i][i + k], cost[i][j] + cost[j+1][i + k]);
				}
				
				cost[i][i + k] += sum[i + k] - sum[i - 1];
			}
		}

		printf("%d\n", cost[1][n]);
	}

}
공유하기